\section{Searching With Boolean Operators}
The advanced part of the project description prescribes us to make the search engine able to support 
the boolean operators \textbf{AND} and \textbf{OR} (once at a time). 
As we wanted to extend the functionality of the search engine, we have made it able to handle more 
complex expressions including both \textbf{AND} and \textbf{OR}-statements in the same query. 
To make it easy for the user to create such queries correctly, it is also possible (for the user) 
to parenthesize the queries. \\

This causes that our implementation of support of boolean operators is much
less simple than what we would make, if we only wanted to fulfill the
requirements of the fifth assignment.

\subsection{How It Works}
In propositional logic conjunction (\textbf{AND}) has higher precedence than disjunction (\textbf{OR}), so it seems natural to follow that convention in our search engine. This means that any \textbf{AND}-parts of the queries are "computed" before any \textbf{OR}-parts, if no parentheses are added. That is, if the user enters a query 
\begin{eqnarray}\label{query1}
word_1 \,\, \textbf{OR} \,\, word_2\,\, \textbf{AND} \,\,word_3,
\end{eqnarray}
the search engine will find all the pages containing either
\begin{enumerate}
\item[a)] $word_1$
\item[b)] both $word_2$ and $word_3$
\item[c)] both a) and b) (all three words)
\end{enumerate}
We must note that the result may not necessarily be the same, if we just read the query in a 
"straightforward" manner, where we first would search for pages containing either $word_1$ or 
$word_2$ (or both) and then finding the pages furthermore containing $word_3$. 
A search like that can also be requested in our search engine. This is simply done by adding 
parentheses around the \textbf{OR}-statement in the original query, as this will give the 
statement in between the parentheses higher precedence than the \textbf{AND}-statement. 
The parentesized query will now be
\begin{eqnarray}\label{query2}
(word_1 \,\, \textbf{OR} \,\, word_2)\,\, \textbf{AND} \,\,word_3.
\end{eqnarray}

Just as a user of a calculator must know that $\cdot$ has higher precedence than $+$ to be able 
to obtain the wished results of simple calculations including product(s) and sum(s), the user of
 our search machine must be familiar with \textbf{AND} having higher precendence than \textbf{OR},
  and that adding parentheses to the expression can change this.

\subsection{Limitations} \label{boolean_limitations}
The search engine is not able to handle every thinkable input properly. As discussed earlier, 
parentheses are allowed - including redundant parentheses to some extent,  eg. queries like 
$(((expression)))$ will be interpreted as $expression$. The important thing
is that the syntax must be correct for the search engine to be able to parse and
search for the query. For example a left parenthesis "$($" must be followed by a
right parenthesis "$)$" and may not be put in the middle of a word. A query must
be on the form $<expression> <operator> <expression>$. We also consider it as a
syntax error if either expression is empty, even though a search is actually
performed. These limitations imply that queries such as
\begin{eqnarray*}
wo)rd\qquad word_1 \, \textbf{OR} \, word_2)( \qquad \, word_1 \textbf{AND}\,
\textbf{OR} word_2 \qquad \, word_1 \,\, word_2
\end{eqnarray*}
 are not meaningful for the search engine. Searching for such expressions will
 not necessarily give reliable results, but the program will never go into an
 infinite loop beacuse of a faulty query. If the search engine is not able to
 interpret the query, it will give the same message to the user as if the no
 results are found on a syntactically correct query; "No match found:
 $<query>$".

 \subsection{Syntax Tree Data Structure}
 For the search engine to be able to interpret the queries including boolean operators, we have 
 created a parse tree data structure. The package \texttt{model.parseTree} contains all the 
 relevant classes for the parse tree. An object of the class \texttt{SyntaxTree} parses a given 
 query, from which it grows a binary tree keeping track of the syntax. This
 is done by the method \texttt{growTree(String query)}, which is called from
 the constructor. It transforms the query into a tree consisting of search
 nodes. There are three different kinds of search nodes: nodes representing
 disjunction and conjunction and nodes representing an actual search word (objects of the classes \texttt{OrNode, AndNode} and \texttt{WordNode}, respectively). All the nodes keep track of their children and thereby their complete subtrees. So when a node is created,
   its child nodes are first created as new instances of \texttt{SyntaxTree}. 
   The word nodes does not have any children - their subtrees are \texttt{null}
   - and hence they are leaf nodes. To actually perform the search on the given query, the method
   \texttt{readTree()} is called on the syntax tree. When a node is being
   evaluated, it will evaluate both its subtrees (left before right), by calling their \texttt{getResult()}-method, before computing and
    returning the combined result. Therefore the only thing \texttt{readTree()}
    does, is to evaluate the rootnode, by calling \texttt{getResult()} on it. The syntax
    trees for the queries given in (\ref{query1}) and (\ref{query2}) are shown in figure \ref{trees}.
 
\begin{figure}
\centering
\subfloat[$word_1 \,\, \textbf{OR} \,\, word_2\,\,
\textbf{AND}\,\,word_3$]{\includegraphics[scale=0.8]{../and_or/query1.pdf}}
\hspace{30pt}
\subfloat[$(word_1 \,\, \textbf{OR} \,\, word_2)\,\, \textbf{AND}
\,\,word_3$]
{\includegraphics[scale=0.8]{../and_or/query2.pdf}}
\caption{Syntax trees for the expressions (\ref{query1}) and (\ref{query2})\label{trees}}
\end{figure}

\subsection{More on Implementation and Time Complexity}
\subsubsection{Growing the tree}
If we look into the implementation of the process of growing the
syntax tree, we will notice that it is quite cumbersome. 
The precedence rules and parentheses adds extra iterations
 of the query to the procedure. We will just explain roughly what is going on in
 the \texttt{growTree()}-method of class \texttt{SyntaxTree}, and afterwards we will look at an example. 
 %\begin{figure}
 %\lstinputlisting[firstline=39,
 %lastline=103]{../../src/model/parseTree/SyntaxTree.java} \caption{Source code
% for the method \texttt{growTree(String query)} fromclass
% \texttt{SyntaxTree}}
% \end{figure}
 The input is a string, which is splitted into separate words. As the splitting is done when a 
space occurs, the parentheses are interpreted as part of the words. (These are properly removed 
when needed). We iterate through all the words one at a time. As soon as an "accepted" boolean 
operator is found, it will be set as the rootnode and the creation of subtrees will begin.
 As \textbf{OR} is of least precedence, we will look for it first, so that it will be evaluated last.
  However, as parentheses can change this, we must first look for \textbf{OR} in the outermost pair 
  of parentheses. If \textbf{OR} is not found there, we must look for \textbf{AND} in the outermost
   pair of parentheses. This means that if we find an  \textbf{OR} somewhere else than in the 
   outermost pair of parentheses it is not accepted at this point. If \textbf{AND} is not found 
   either, we must proceed to the next "level" of parentheses, and start over
   again. Now \textbf{OR} will be accepted only if it is in the next outermost
   pair of parentheses and so on, until we reach the innermost pair of
   parentheses. The local variable \texttt{parCounter} of type \texttt{int}
   will keep track of the parentheses. It increments when a ( is found and
   decrements when a ) is found.\\
   
We will now demonstrate the execution of \texttt{growTree(example)} on an
example (for convenience of reading, the "" enclosing Strings are left out):
\begin{eqnarray*}
Hans \,\, \textbf{AND} \,\,(Grethe \,\,\textbf{OR} \,\,pandekagehus)
\end{eqnarray*}
To begin with, the level of parentheses we search in is 0, the parentheses
counter is 0, the operator index is 0 - which means that we search for the
operator \textbf{OR} outside any parentheses. The query is splitted into an
array of separate words: $[Hans,\, \textbf{AND},\, (Grethe,\, \textbf{OR},\,
pandekagehus)]$
which will be considered one at a time in the inner \texttt{while}-loop. When a
word is considered, the parentheses are ignored. The \textbf{OR} will be
discarded in first iteration as the \texttt{parCounter} is 1 (not 0). In the
next iteration the operator index is 1, so we search for \textbf{AND} within 0
parentheses. Hence \textbf{AND} will be the rootnode, and new child
\texttt{Syntaxtree}s will be created from $Hans$ and $(Grethe \,\,\textbf{OR}
\,\,pandekagehus)$. A word node with $Hans$ will be created in left subtree. In
right subtree, a node with \textbf{OR} will be created after searching for both
\textbf{OR} and \textbf{AND} outside parentheses and then finding \textbf{OR}
inside one pair of parentheses. At last word nodes with $Grethe$ and
$pandekagehus$ will be created.

\subsubsection{Time Complexity}
Let $n$ denote the number of words in the query (actual search words as well as boolean operators) 
and let $m$ denote the number of pairs of start and end parentheses. We assume that checking if a 
word is a boolean operator or not can be done in constant time. Then the time for finding a boolean 
operator is $O(nm)$. The number of boolean operators in a (syntactically
correct) query can be up to $\frac{n}{2}-1$, which is $O(n)$. Hence the time for
finding all boolean operators is $O(n^2 m)$ in the worst case.

Reading the tree depends on the time to search for the actual search words,
which again depends on which data structure we search in. However, making the
\texttt{getResult()}-calls to all nodes can be done in linear time.

\subsubsection{Possible Changes}
\begin{itemize}
\item In section \ref{boolean_limitations} we described how syntax errors in a
query is handled. We could choose to change this in different ways. One possibility is
to let the the program guess what is meant by the faulty query, and then rewrite it to a syntactically
 correct expression before evaluating it. Another possibility is to give a message to the user, 
saying that the syntax was wrong, instead of performing any search. This could
possibly be done with exception handling.
\item We could have made the search nodes of the syntax tree of enumerated type,
to ensure that they could only be the valid ones.
\item We could add a fourth kind of search node - a \textbf{NOT}-node, to make
it possible to search for URLs on which some specific word does \textit{not}
occur.
\item We could have used already existing classes to parse a query instead of
building our own.
\end{itemize}